//
// Created by user on 2022/4/11.
//
#include <iostream>
#include <unordered_map>
using namespace std;

//递归
int fib(int n) {
    if (n==1)return 1;
    if(n==0)return 0;
    return fib(n-2)+fib(n-1);
}
unordered_map<int, int> map;
int dfs(int n);

//记忆化搜索
int fib1(int n) {
    return dfs(n);
}

int dfs(int n){
    if (n==1)return 1;
    if(n==0)return 0;
    if (map.count(n)){
        return map.find(n)->second;
    }
    int left = dfs(n-1);
    int right = dfs(n-2);
    map.insert(make_pair(n, left+right));
    return left+right;
}

//数组构建、
int dfs2(int n, vector<int> memo);
int fib2(int n) {
    vector<int> memo(n+1, -1);
    return dfs2(n, memo);
}

int dfs2(int n, vector<int> memo){
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != -1) return memo[n];
    int leftFib = dfs(n - 1);
    int rightFib = dfs(n - 2);
    memo[n] = leftFib + rightFib;
    return memo[n];
}

//自底而上
// 动态规划的四个步骤
int fib3(int n) {
    if (n <= 1) return n;
    // 1. 定义状态数组，dp[i] 表示的是数字 i 的斐波那契数
    vector<int> dp(n + 1);

    // 2. 状态初始化
    dp[0] = 0;
    dp[1] = 1;

    // 3. 状态转移
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    // 4. 返回最终需要的状态值
    return dp[n];
}

//状态空间压缩
int fib4(int n) {
    if (n <= 1) return n;
    int prev = 0;
    int curr = 1;


    // 3. 状态转移
    for (int i = 2; i <= n; i++) {
        int tmp = curr +prev;
        prev = curr;
        curr = tmp;

    }

    // 4. 返回最终需要的状态值
    return curr;
}